package com.tgy.programmer_code_interview_guide._01_stack_queue;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 1/19/21 9:44 AM
 */
public class _07_构造数组的MaxTree_递归 {

    public static Node generalArrayMaxTree(int[] arrs) {

        if (arrs == null || arrs.length == 0) {

            return null;
        }

        return general(arrs, 0, arrs.length - 1);
    }

    /**
     * log(n) * n
     * @param arrs
     * @param start
     * @param end
     * @return
     */
    private static Node general(int[] arrs, int start, int end) {


        Node root = new Node(arrs[start]);
        if (start == end) {

            return root;
        }

        int maxIndex = findMaxIndex(arrs, start, end);
        root.value = arrs[maxIndex];
        if (maxIndex > start) {

            root.left = general(arrs,start,maxIndex - 1);
        }

        if (maxIndex < end) {

            root.right = general(arrs,maxIndex + 1, end);
        }

        return root;
    }

    /**
     *
     * O(n)
     */
    private static int findMaxIndex(int[] arrs, int start, int end) {

        if (start == end) {

            return start;
        }

        int index = start;

        for(int i = start + 1; i <= end; i++) {

            if (arrs[i] > arrs[index]) {

                index = i;
            }
        }

        return index;
    }

    public static void main(String[] args) {
//
       Node root = generalArrayMaxTree(new int[]{4,2,5,1,3});
//       Node root = generalArrayMaxTree(new int[]{3,4,5,1,2});

        System.out.println(root);
    }
}
